分布式统计计算方法简介

（图片来源：https://techcrunch.com/2021/07/15/cockroachdb-ec1-developers/）

背景介绍

毫无疑问，我们正生活在一个高速发展的信息时代。不论是进行一次网上购物，还是向上滑去一个短视频，抑或是搜索一个关键词，我们每个人在与手机交互过程中就产生了大量的数据。服务提供商当然希望对这些数据进行统计分析，进而为我们提供更加个性化的服务，例如进行商品推荐。但如今几乎每个人都有一部智能手机，因此可以想象，大家每天产生的数据量是非常庞大的。以搜索引擎谷歌为例，它在全球有许许多多的服务站点，其中每个站点每天就可以收集到TB级别的数据。很显然，由于网络带宽以及单台服务器性能的限制，谷歌肯定不会将所有数据传输到一台服务器上进行统计分析。那么，针对这种分布式存储的数据，能否设计一些分布式计算框架来提高计算效率呢？

答案当然是肯定的。与并行计算类似，分布式计算（distributed computing）的思想也来源于“分而治之”（divide-and-conquer）的策略。简单来说，对于一个大规模的统计计算问题，如果我们可以把它分成一些可以同时进行的小任务，然后让多个CPU或者计算机对它们分别进行处理，那么将会大大地减少计算时间。以一个简单的问题为例：假设有N个样本点被存储在K台局部机器（local machine）上，如何计算全样本的的平均值？很简单，我们只需让每台局部机器计算本地子样本的均值，然后把它和子样本量发送给一台中心机器（central machine，中心机器常常是K台局部机器中的一台）。中心机器接收到每个子样本的均值和样本量后，便可以通过加权平均算出全样本的均值。在这个过程中，我们把“计算全样本均值”这个任务划分成K个可同时进行的“计算子样本均值”的小任务，从而将计算时间几乎缩减成原来的1/K（如果忽略传输信息的时间）。

当然，上面的例子过于简单，实际问题往往要复杂很多。事实上，大多数时候，在分布式场景下很难直接计算基于全样本的估计量。比如在刚才的例子中，如果把平均数换成中位数，这个问题似乎就没那么简单了。因为即使我们知道每个子样本的中位数和样本量，也很难把它们组合成全样本的中位数。此外，分布式计算与传统的并行计算也有一定区别。传统的并行计算系统中，各个处理器常常是共享同一块内存的，因此能够以极快的速度进行数据的交互。然而，分布式计算框架中的各台机器往往是物理隔离的，他们仅靠网线连接在一起。因此在设计分布式算法的时候，还需要考虑到机器间进行数据通讯的时间消耗。

基于对以上这些问题的考量，在为统计问题设计分布式算法时需要权衡估计精度、通讯成本、计算时间这三个维度。虽然在分布式场景下一般很难获取基于全样本的估计量，但还是希望最终得到的分布式估计量（distributed estimator）与全样本估计量（whole sample estimator，WSE）具有十分接近的表现。一般来说，全样本估计量具有最优的估计精度，但计算时间也是最长的（数据量太大时甚至无法计算）。可是如果使用的机器过多，虽然可以大幅度降低单台机器的计算时间，但得到的分布式估计量的统计性质可能会很差。这一点通常可以通过增加机器间的数据交互来弥补，然而同时又会带来极大的通讯成本。因此，如何平衡好这三个方面对一个分布式算法来说是十分关键的。

接下来，我们根据机器间数据交互的形式将分布式计算框架分为单轮型和迭代型两大类，并分别简要叙述它们的大致思想和特点。接着以主成分分析为例，介绍了一个略有不同的分布式算法。最后对全文进行总结。

单轮型方法 （One-shot approach）

在各种分布式计算框架中，单轮型（one-shot）方法是一类较为简单直接的方法。所谓的“单轮”指的是“每台局部机器只与中心机器进行一次通讯”。单轮型方法的大致步骤如下：

（1）每台局部机器基于本地的子样本计算相关的估计量或者统计量，然后发送给中心机器。

（2）中心机器对局部机器所发送的统计量进行有机整合，得到最终的分布式估计量。

单轮型方法的示意图如图1所示。可以看到，整个算法的框架较为简单。不同单轮型算法之间的区别主要在“整合局部估计量”这一步。

图1单轮型方法示意图

最简单的一种整合方法就是对局部估计量做简单平均，所得到的分布式估计量也被称为简单平均估计量（simple averaging estimator，SAE）。具体地，我们下面考虑一个一般的参数估计问题。为了简单起见，我们假设N个样本点被平分到K台局部机器上，使得每台机器有n个样本点。这时候，每台局部机器通过优化子样本所构造的损失函数来得到局部估计量，并将其发送给中心机器。最后，中心机器将这些局部估计量做平均，便得到了简单平均估计量（SAE）：

SAE的计算十分简单和直接，它的统计学性质也得到了充分的研究。例如Zhang et al. 给出了SAE的均方误差（MSE）上界：

其中表示待估参数的真值。我们知道，在通常的参数估计问题中，全样本估计量（WSE）的MSE收敛速度一般为O(1/N)。对比这两个收敛速度，我们可以发现当时，SAE的MSE可以达到与WSE相同的收敛阶。但同时我们也可以看到，SAE要想达到WSE的估计精度，局部机器数K不能超过局部样本量n，这意味着我们不能把全样本分成太多份。

除了使用平均来整合局部估计量以外，还有一些其他的方式。例如使用KL-散度 (Liu and Ihler, 2014)：

在样本来自指数分布族时，可以证明这个分布式估计量具有与全样本极大似然估计（MLE）相媲美的优良性质。还有些时候，某些局部机器可能会由于异常值的影响算出完全错误的估计量。如果仍然使用平均的方式来整合局部估计量，异常的局部估计量会严重降低SAE的有效性。因此，Minsker (2019)提出了更加稳健（robust）的聚合方式：

其中是一个稳健的损失函数。例如时，得到估计实际上就是所有局部估计量的中位数。很显然，相较于均值，中位数对于异常估计值更加稳健。

一般来说，单轮型分布式算法简单且容易实现，而且具有较低的通讯成本。以SAE为例，每台局部机器只需向中心机器传输一个局部估计量。假设待估参数的维数为p，那么数据传输总量只有O(Kp)这个量级。同时，因为机器间交互的信息较少，在一些复杂的估计问题中，SAE的表现可能会不太好。例如在高维收缩估计（shrinkage estimation）问题中，我们一般很难得到无偏估计量（unbiased estimator）。此时，简单的平均无法降低局部估计量的偏差至WSE的偏差水平。一种方法是先对局部估计量做纠偏处理，然后再进行整合。这方面的工作可以参考Lee et al. (2017)

迭代型方法 (Iterative approach)

上一节我们简要介绍了单轮型分布式算法，这类算法具有简单易操作、通讯成本低等优点。但同时也发现，由于机器间信息交互十分有限，此类算法常常需要足够多的局部样本量来保证最终估计量的精度。这实际上限制了我们调用更多机器来缩减计算时间。因此，研究者们开始提出一些迭代型方法，打破了单轮型方法对机器数的限制。迭代型方法，顾名思义，就是指算法需要在机器间进行多轮迭代，也意味着局部机器与中心机器间会有多轮通讯。不同的迭代型算法之间可能有较大差异，但大致有如下步骤：

（1）每台局部机器基于本地所储存的子样本计算相关的统计量（例如局部损失函数的梯度、黑塞矩阵等等），然后发送给中心机器。

（2）中心机器利用这些局部统计量计算参数的估计值，并将其返回给每台局部机器。

（3）局部机器根据更新后的参数估计值，重新计算相应的统计量，并发送给中心机器。

（4）根据精度需求，重复步骤（2）-（3）若干轮。

图2给出了迭代型方法的示意图。接下来，我们介绍比较几个比较典型的算法。

图 2 迭代型方法示意图

在参数估计问题中，我们常常比较容易获取一个相合（consistent）估计量，但得到一个有效（efficient）估计量相对较难。例如上文提到的简单平均估计量（SAE），它是一个√N相合估计量，但它的渐进方差常常不是最优的。也就是说，SAE没有充分利用样本所蕴含的信息。在统计学中，有一种提高相合估计量有效性的方法，被称为“一步法”（one-step method）。这里的“一步”指的是，在现有的相合估计量基础上，利用似然函数（或损失函数）再做一步牛顿迭代（Newton-Raphson iteration）。所得到的新估计量也被称为一步估计量（one-step estimator）。Huang and Huo (2019)将该方法应用到了分布式框架下：(1) 中心机器算得SAE后将其发送给各局部机器；(2) 局部机器计算本地损失在SAE处的梯度和黑塞矩阵并返回给中心机器；(3) 中心机器利用这些梯度和黑塞矩阵计算一步估计量（注意到，这些局部梯度和黑塞矩阵的均值就是相应的全样本梯度及黑塞矩阵）：

Huang and Huo (2019)也给出了一步估计的MSE上界：

与SAE的MSE相比可以看到，一步估计具有更小的高阶误差项，因此放松了对局部样本量的需求。此外，该文章也证明了该估计量与全局MLE拥有相同的渐进分布，表明了一步估计量的有效性。

很显然，一步估计方法可以直接推广为多步估计，使相应的估计量更加接近全局估计量（WSE）的估计精度。但是可以看到，由于算法需要传输梯度和黑塞矩阵，每迭代一轮的通讯量为。如果待估参数的维数p过高的话，整个算法的通讯成本也会非常高。因此，相关研究者提出了一些通讯有效的（communication-efficient）迭代型算法。这方面的一个典型工作为近似牛顿法（approximate Newton-type method）。注意到，一步估计方法中额外的通讯量来源于p × p维黑塞矩阵的传输。因此，Shamir et al. (2014) 提出将牛顿迭代法中的黑塞矩阵替换为中心机器本地的黑塞矩阵：

此时，局部机器只需向中心机器发送梯度向量即可。此时，每迭代一轮的通讯量降低为O(Kp)，这与SAE的通讯量相同。Jordan et al. (2019) 使用了类似的技术，并得到如下结果：

也就是说，每迭代一轮，估计量与WSE之间的差距可以缩小为原来的。因此，迭代几步便可以得到和WSE统计性质相匹配分布式估计量。

近似牛顿法是迭代型方法中用来节省通讯量的常用技巧，例如在分布式支持向量机算法(Wang, Yang et al., 2019)中 也用到了类似的技术。但是，当各台机器上的样本存在一些异质性时，中心机器本地的黑塞矩阵可能无法很好地代表每个局部损失函数的二阶信息。此时，该方法可能无法得到很好的估计量。关于这方面的讨论可以参考Fan, Guo et al. (2019)。总的来说，迭代型方法通过增加通讯量，提高了分布式估计量的精度，同时放宽了对局部机器数的限制。但在设计相应的算法时，通讯成本也须慎重考虑。

例子：主成分分析

上文提到的一些方法大多针对的是M-估计问题，即优化特定的损失函数（似然函数）来获取参数的估计。下面我们考虑一个不同的问题：如何针对分布式储存的数据进行主成分分析(principal component analysis, PCA)。主成分分析是一种非常有效的归约数据的方式，可以帮助我们简化原始数据，并保留其中的“主要因子”。PCA的核心步骤就是找到原始数据的主成分方向，而主成分方向就是数据的协方差阵的前几个特征向量。因此，我们只需对样本协方差阵做特征分解即可（或者直接对原始数据矩阵进行奇异值分解（SVD））。

在分布式的设定下，一个很简单直接的想法是：对每个子样本的前d个主成分方向做简单平均。但显然这种聚合方式是很糟糕的，因为它没法保证最后得到的各个主成分方向还具有正交性。Fan, Wang et al. (2019) 提出了一种单轮型分布式算法来估计主成分方向，大致步骤如下：

（1）计算每个子样本的前d个主成分方向，并按列组成矩阵，然后发送给中心机器。

（2）中心对每个对应的投影矩阵做简单平均，得到；再对做特征分解，并取前d个特征向量作为主成分方向。

由于该算法得到的主成分方向是矩阵的特征向量，因此它们的正交性得到了保证。此外，该文章也证明了当局部样本量足够多的时候，主成分方向的分布式估计与全样本估计有着相同的误差收敛速度。

总结

这篇小文简单介绍了分布式统计计算的基本思想，并分析比较了单轮型和迭代型这两大类分布式框架各自的特点：单轮型方法简单易实施，但需要足够的局部样本量；迭代型方法更加灵活，允许调用更多局部机器。在这些不同的分布式算法中，估计精度、通讯成本、计算时间始终是需要被认真考虑的因素。在本文中，我们默认了数据是平均、随机地分配到各台机器的。但这并不符合实际情况：不同机器上的样本量常常有很大差别，而且这些数据的分布往往也不尽相同。对于这种数据分配不平均、不随机的情形，可以参考Wang and Zhu et al. (2021)中的讨论。此外，由于篇幅有限，本文跳过了对收缩估计、非参数估计等问题的讨论，有兴趣的读者可以参考下面这篇综述性文章：

Gao Y, Liu W, Wang H, et al. A review of distributed statistical inference[J]. Statistical Theory and Related Fields, 2021:1-11. https://doi.org/10.1080/24754269.2021.1974158

参考文献

[1] Zhang Y, Duchi J C, Wainwright M J. Communication-efficient algorithms for statistical optimization[J]. The Journal of Machine Learning Research, 2013, 14(1): 3321-3363.

[2] Liu Q, Ihler A T. Distributed Estimation, Information Loss and Exponential Families[J]. Advances in Neural Information Processing Systems, 2014, 27: 1098-1106.

[3] Minsker S. Distributed statistical estimation and rates of convergence in normal approximation[J]. Electronic Journal of Statistics, 2019, 13(2): 5213-5252.

[4] Lee J D, Liu Q, Sun Y, et al. Communication-efficient sparse regression[J]. The Journal of Machine Learning Research, 2017, 18(1): 115-144.

[5] Huang C, Huo X. A distributed one-step estimator[J]. Mathematical Programming, 2019, 174(1): 41-76.

[6] Shamir O, Srebro N, Zhang T. Communication-efficient distributed optimization using an approximate newton-type method[C]//International conference on machine learning. PMLR, 2014: 1000-1008.

[7] Jordan M I, Lee J D, Yang Y. Communication-efficient distributed statistical inference[J]. Journal of the American Statistical Association, 2018.

[8] Wang X, Yang Z, Chen X, et al. Distributed inference for linear support vector machine[J]. Journal of machine learning research, 2019, 20.

[9] Fan J, Guo Y, Wang K. Communication-efficient accurate statistical estimation[J]. Journal of the American Statistical Association, 2021 (just-accepted): 1-29.

[10] Fan J, Wang D, Wang K, et al. Distributed estimation of principal eigenspaces[J]. Annals of statistics, 2019, 47(6): 3009.

[11] Wang F, Zhu Y, Huang D, et al. Distributed one-step upgraded estimation for non-uniformly and non-randomly distributed data[J]. Computational Statistics & Data Analysis, 2021, 162: 107265.

- END -